#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5+100;
const int mod=1e9+7;
typedef long long LL;
inline LL read(){LL x=0,f=1;char ch=getchar();	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
vector<int>g[31];
int dp[2][1<<12];
int a[maxn];
int primes[]={2,3,5,7,9,11,13,17,19,23,29};
int state[maxn];
void init()
{
    memset(dp,0,sizeof(dp));
    memset(state,0,sizeof(state));
    for(int i=1;i<=30;i++) g[i].clear();
    for(int i=1;i<=30;i++){
        bool flag=true;
        int temp=i;
        for(int j=2;j<=sqrt(temp);j++)
        {
            if(temp%j==0)
            {
                int cnt=0;
                while(temp%j==0)
                {
                    cnt++;temp/=j;
                }
                if(cnt>=2) flag=false;
                g[i].push_back(j);
            }
        }
        if(temp>1) g[i].push_back(temp);

        if(flag==false) g[i].clear();
        else{
            int st=0;
            for(int k=0;k<g[i].size();k++)
            {
                for(int o=0;o<11;o++)
                {
                    if(g[i][k]==primes[o])
                    {
                        st|=1<<o;
                    }
                }
            }
            state[i]=st;
        }
    }
//    for(int i=1;i<=30;i++)
//    {
//        cout<<"i="<<i<<"  state["<<i<<"]="<<state[i]<<endl;
//    }
}
int numberOfGoodSubsets(vector<int>& nums) {
    init();
    for(int i=0;i<nums.size();i++) a[i+1]=nums[i];
    //dp[0]=1;
    int ans=0;
    int now=0;
    int allstate=1<<11;int n=nums.size();
    for(int i=1;i<=n;i++)
    {
        //dp[now][0]=1;

        if(g[a[i]].empty()) continue;

        int nowstate=state[a[i]];

        dp[now][nowstate]+=1%mod;

        for(int j=0;j<allstate;j++)
        {
            //cout<<"j="<<j<<" "<<j<<"^"<<nowstate<<"="<<(j^nowstate)<<endl;
            dp[now][j]+=dp[now^1][j^nowstate]%mod;
            ans+=dp[now][j]%mod;
            //cout<<"dp["<<now<<"]["<<j<<"]="<<dp[now][j]<<endl;
        }
        for(int j=0;j<allstate;j++) dp[now^1][j]=0;
        now^=1;
    }
    return ans;
}
int main(void){
    vector<int>nums;
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        nums.push_back(x);
    }
    cout<<numberOfGoodSubsets(nums)<<endl;
   	return 0;
}
